package leetcode.editor.vscdev.hot100;

import leetcode.editor.utils.*;

public class lc143 {
    /*
     * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
     * L0 → L1 → … → Ln - 1 → Ln
     * 请将其重新排列后变为：
     * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
     * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     */
}

class Solution {
    public void reorderList(ListNode head) {
        // 遍历到中点
        ListNode midNode = getMidNode(head);
        ListNode next = midNode.next;
        midNode.next = null;
        next = reverse(next);
        merge(head, next);
    }

    // 获取中点
    private ListNode getMidNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 反转链表
    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 合并链表
    private void merge(ListNode list1, ListNode list2) {
        while (list1 != null && list2 != null) {
            ListNode list1Next = list1.next;
            ListNode list2Next = list2.next;
            list1.next = list2;
            list2.next = list1Next;
            list1 = list1Next;
            list2 = list2Next;
        }
    }
}
